Shrinking restarting automata

Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

Entwicklung und Validierung der Steigbildmethode zur Differenzierung von ausgewählten Lebensmitteln aus verschiedenen Anbausystemen und Verarbeitungsprozessen

Zusammenfassung (deutsch) Seit den 1980iger Jahren wächst die Bedeutung der sog. Bildschaffenden Methoden für die Bestimmung der Qualität ökologischer Produkte. Zu diesen Methoden gehört die Biokristallisation, Steigbild und Rundfilter-Chromatographie. Die Ergebnisse dieser Methoden sind Bilder, die anhand definierter Kriterien ausgewertet werden. Bei der Biokristallisation sind es mehr oder weniger geordnete Kristallisationen auf einer Glasplatte, bei dem Steigbild zweidimensionale Strukturen auf Chromatographiepapier. In der Vergangenheit wurden die Bilder von Spezialisten ausgewertet, die nach einer längeren Schulung produktspezifische Kriterien entwickelt hatten. Im Gegensatz zur Dünnschicht-Chromatographie, wo der einzelne Stoff von der Matrix separiert wird, ist das Ziel beim Steigbild, Strukturen der möglichst ganzen Probe zu erzeugen. Die Methode wurde von Kolisko in den 1929iger Jahren entwickelt, wobei eine Kombination aus Chromatographieprozess und Metallkomplexreaktionen genutzt wurde. Die Firma WALA entwickelte die Methode für die Kontrolle ihrer Produkte und setze Silbernitrat und Eisensulfat ein. Bisher wurde die Methode qualitativ beschreibend ausgewertet, wobei einzelne Bildelemente und deren Interaktion beschrieben wurden. Deshalb musste für die vorliegende Arbeit Auswertungsmethoden entwickelt werden, mit denen auch eine statistische Bearbeitung der Ergebnisse möglich ist (nominale Unterscheidung von proben anhand der Bilder). Die Methode wurde bisher in einer Reihe von Studien eingesetzt (u.a. die Unterscheidung von Produktionsweisen). Obwohl die Bilder nur qualitativ ausgewertet wurden, konnten geschulte Prüfpersonen Proben aus verschiedenen Anbausystemen anhand der Bilder trennen. Die Ergebnisse wurden aber nicht so dokumentiert, dass sie den Erfordernissen internationaler Standardnormen für Laboratorien genügten. Deshalb mussten für diese Arbeit zunächst die Prozeduren dokumentiert und eine systematische Untersuchung zu den Einflussgrößen durchgeführt werden. Dazu wurde die visuelle Bildauswertung entwickelt und standardisiert. Die visuelle Bildauswertung basiert auf morphologischen Kriterien der Bilder von den untersuchten Weizen- und Möhrenproben. Ein Panel aus geschulten Personen entwickelte dann die Kriterien und legte sie anhand von Referenzbildern fest. Die Bilder der vorliegenden Arbeit wurden mit der einfach beschreibenden Prüfung ausgewertet, wie sie aus der sensorischen Prüfung von Lebensmitteln übernommen werden konnte. Mit geschulten und ungeschulten Prüfpersonen wurden Weizenproben und verschiedene Möhrensäfte mit der sog. Dreiecksprüfung ausgewertet (von ISO 4120). Alle Laborprozeduren wurden dokumentiert. Mit der Anwendung dieser Prozeduren wurden Vergleichsversuche mit Laboren in Dänemark und Holland (BRAD, LBI) durchgeführt. Die Ergebnisse waren sowohl für Weizen- als auch für Möhrenproben vergleichbar, wobei alle drei Labore zwischen jeweils zwei Proben unterscheiden konnten. Die systematische Untersuchung zu den Einflussgrößen zeigte, dass das Unterscheidungsvermögen der Methode vor allem von den klimatischen Bedingungen während der Steigphasen beeinflusst wird. Auch die Präkonditionierung der Papiere hat einen großen Einfluss, während die Wasserqualität (ultra-filtriert, de-ionisiert, destilliert) eine untergeordnete Bedeutung hat. Für Weizen- und Möhrenproben wurde sowohl die Wiederholbarkeit als auch die Reproduzierbarkeit getestet. Die Unterschiede in den Bildern der verschiedenen Proben waren dabei immer größer als die Variation durch Proben- und Bildwiederholung und das Labor. Die so charakterisierte Methode wurde auf kodierte Proben von definierten Feldversuchen und auf Marktproben (Paarvergleich von Anbausystemen ökologisch und konventionell) angewandt, wobei als Ergebnis mehr als 90% der Proben mit der einfach beschreibenden Prüfung anhand der Bilder unterschieden werden konnten. Die Auswertung mit der Dreiecksprüfung zeigte, dass sowohl Sorten und Verarbeitungsschritte (Saft) als auch Anbauweisen signifikant getrennt wurden. Darüber hinaus wurde die Methode auch erfolgreich auf Apfelproben angewandt. Weitere Untersuchungen müssen zeigen, ob sich das Potential der Methode, verschiedene Fragen wie die Authentizitätsprüfung von Lebensmitteln verifizieren lassen.

Three-electron radiative transitions

A new type of many-electron radiative transitions involving three electrons is predicted. The results of their investigation by many-body perturbation theory are presented. New spectral lines observed in the wavelength range of 37.5 to 54.0 nm by means of photon-induced fluorescence spectroscopy (PIFS) following the excitation of the Kr I 3d{^-1}np resonances are reported and compared with the predictions.

Hyperfine structure and isotopic shift of the n^2 P_J levels (n = 7-10) of ^203,205 TI measured by Doppler-free two-photon spectroscopy

Using Doppler-free two-photon absorption spectroscopy, we have measured hyperfine splitting constants as well as isotopic level shifts of the 6s^2 np ^2 P_l/2,3/2 states in (n=7-10) in ^203 TI and ^205 TI. Calculations for hyperfine constants and electron density at the nucleus have been performed by the Dirac-Fock method. The experimental results are compared with these calculations as well as with the predictions of the semiempirical theory.

Preparation and applications of periodical gold nanoparticle arrays

Diese Arbeit beschäftigt sich mit der Herstellung und Anwendungen von periodischen Goldnanopartikel-Arrays (PPAs), die mit Hilfe von Nanosphären-Lithografie hergestellt wurden. In Abhängigkeit der verwendeten Nanosphären-Größe wurden dabei entweder kleine dreieckige Nanopartikel (NP) (bei Verwendung von Nanosphären mit einem Durchmesser von 330 nm) oder große dreieckige NPD sowie leicht gestreckte NP (bei Verwendung von Nanosphären mit einem Durchmesser von 1390 nm) hergestellt. Die Charakterisierung der PPAs erfolgte mit Hilfe von Rasterkraftmikroskopie, Rasterelektronenmikroskopie und optischer Spektroskopie. Die kleinen NP besitzen ein Achsverhältnis (AV) von 2,47 (Kantenlänge des NPs: (74+/-6) nm, Höhe: (30+/-4) nm. Die großen dreieckigen NP haben ein AV von 3 (Kantenlänge des NPs:(465+/-27) nm, Höhe: (1530+/-10) nm) und die leicht gestreckten NP (die aufgrund der Ausbildung von Doppelschichten ebenfalls auf der gleichen Probe erzeugt wurden) haben eine Länge von (364+/-16)nm, eine Breite von (150+/-20) nm und eine Höhe von (150+/-10)nm. Die optischen Eigenschaften dieser NP werden durch lokalisierte Oberflächenplasmon-Polariton Resonanzen (LPPRs) dominiert, d.h. von einem eingestrahlten elektromagnetischen Feld angeregte kollektive Schwingungen der Leitungsbandelektronen. In dieser Arbeit wurden drei signifikante Herausforderungen für Plasmonik-Anwendungen bearbeitet, welche die einzigartigen optischen Eigenschaften dieser NP ausnutzen. Erstens wurden Ergebnisse der selektiven und präzisen Größenmanipulation und damit einer Kontrolle der interpartikulären Abstände von den dreieckigen Goldnanopartikel mit Hilfe von ns-gepulstem Laserlicht präsentiert. Die verwendete Methode basiert hierbei auf der Größen- und Formabhängigkeit der LPPRs der NP. Zweitens wurde die sensorischen Fähigkeiten von Gold-NP ausgenutzt, um die Bildung von molekularen Drähten auf den PPAs durch schrittweise Zugabe von unterschiedlichen molekularen Spezies zu untersuchen. Hierbei wurde die Verschiebung der LSPPR in den optischen Spektren dazu ausgenutzt, die Bildung der Nanodrähte zu überwachen. Drittens wurden Experimente vorgestellt, die sich die lokale Feldverstärkung von NP zu nutze machen, um eine hochgeordnete Nanostrukturierung von Oberflächen mittels fs-gepulstem Laserlicht zu bewerkstelligen. Dabei zeigt sich, dass neben der verwendeten Fluenz die Polarisationsrichtung des eingestrahlten Laserlichts in Bezug zu der NP-Orientierung sowie die Größe der NP äußerst wichtige Parameter für die Nanostrukturierung darstellen. So konnten z.B. Nanolöcher erzeugt werden, die bei höheren Fluenzen zu Nanogräben und Nanokanälen zusammen wuchsen. Zusammengefasst lässt sich sagen, dass die in dieser Arbeit gewonnen Ergebnisse von enormer Wichtigkeit für weitere Anwendungen sind.

Unsymmetrisch substituierte N-heterocyclische Carbene mit einem 1,1 ʹ-Ferrocendiyl-Rückgrat und N-heterocyclische Carbene als Adsorbatspezies für selbstorganisierende Monolagen

Aufbauend auf den Arbeiten von Bielawski et al. und Siemeling et al. wurden im Rahmen dieser Arbeit unsymmetrisch substituierte N-heterocyclische Carbene mit einem 1,1ʹ-Ferrocendiyl-Rückgrat synthetisiert. Ausgehend von der literaturbekannten Verbindung 1,1’-Diaminoferrocen gelang die Einführung der exocyclischen Substituenten an den Stickstoffatomen lediglich durch die Anpassung der Stöchiometrie in den einzelnen Syntheseschritten. Es wurden die folgenden drei NHCs synthetisiert: N-(2-Adamantyl)-N’-neopentyldiaminocarben[3]ferrocenophan (Ad/Np), N-Neopentyl-N’-phenyldiaminocarben[3]ferrocenophan (Ph/Np) und N-(9-Anthracenylmethyl)-N’-neopentyldiaminocarben[3]ferrocenophan (Acm/Np). Das Carben Ad/Np konnte dabei erfolgreich isoliert werden, während die anderen zwei Carbene als Liganden in Komplexen des Typs [RhCl(COD)(NHC)] stabilisiert wurden. Von allen drei Carbenen wurden Rhodium-Carben-Komplexe des Typs [RhCl(COD)(NHC)] und cis-[RhCl(CO)2(NHC)] synthetisiert. Anhand der röntgenkristallographischen und NMR-spektroskopischen Untersuchungen dieser Rhodiumkomplexe konnten in allen sechs Komplexen anagostische Wechselwirkungen zwischen dem zentralen Rhodiumatom und den Wasserstoffatomen der exocyclischen Substituenten, die sich in α-Position zu den Stickstoffatomen befinden, nachgewiesen werden. Des Weiteren wurden anhand der cis-[RhCl(CO)2(NHC)]-Komplexe die TEP-Werte der Carbene bestimmt. Gemessen in DCM betragen diese 2049 cm-1 (Ad/Np), 2049 cm-1 (Ph/Np) und 2051 cm-1 (Acm/Np). Unabhängig von den unsymmetrisch substituierten NHCs mit einem 1,1ʹ-Ferrocendiyl-Rückgrat wurde im Rahmen dieser Arbeit die Eignung von NHCs als Adsorbatspezies für selbstorganisierende Monolagen überprüft. Hierzu wurden Tetraalkylimidazol-2-ylidene synthetisiert, welche als 0.01 mM Lösung auf Gold(111)-Substrate aufgebracht wurden. Die Goldsubstrate wurden anschließend mittels XPS untersucht. Die XPS-Analyse der modifizierten Goldsubstrate zeigte, dass eine Bindung der Carbene auf der Oberfläche stattgefunden hat. Es zeigte sich allerdings auch, dass keine SAM gebildet wurden, da die Oberfläche signifikant mit kohlen- und sauerstoffbasierten Verbindungen kontaminiert ist. Dabei kann vermutet werden, dass die Carbene nicht ausschließlich auf der Goldoberfläche selbst, sondern auch mit den auf der Oberfläche befindlichen Verbindungen reagiert haben.

Modellbildung in der algebraischen Kryptoanalyse

In der algebraischen Kryptoanalyse werden moderne Kryptosysteme als polynomielle, nichtlineare Gleichungssysteme dargestellt. Das Lösen solcher Gleichungssysteme ist NP-hart. Es gibt also keinen Algorithmus, der in polynomieller Zeit ein beliebiges nichtlineares Gleichungssystem löst. Dennoch kann man aus modernen Kryptosystemen Gleichungssysteme mit viel Struktur generieren. So sind diese Gleichungssysteme bei geeigneter Modellierung quadratisch und dünn besetzt, damit nicht beliebig. Dafür gibt es spezielle Algorithmen, die eine Lösung solcher Gleichungssysteme finden. Ein Beispiel dafür ist der ElimLin-Algorithmus, der mit Hilfe von linearen Gleichungen das Gleichungssystem iterativ vereinfacht. In der Dissertation wird auf Basis dieses Algorithmus ein neuer Solver für quadratische, dünn besetzte Gleichungssysteme vorgestellt und damit zwei symmetrische Kryptosysteme angegriffen. Dabei sind die Techniken zur Modellierung der Chiffren von entscheidender Bedeutung, so das neue Techniken entwickelt werden, um Kryptosysteme darzustellen. Die Idee für das Modell kommt von Cube-Angriffen. Diese Angriffe sind besonders wirksam gegen Stromchiffren. In der Arbeit werden unterschiedliche Varianten klassifiziert und mögliche Erweiterungen vorgestellt. Das entstandene Modell hingegen, lässt sich auch erfolgreich auf Blockchiffren und auch auf andere Szenarien erweitern. Bei diesen Änderungen muss das Modell nur geringfügig geändert werden.

Eigenschaften chromatischer Polynome

Die Berechnung des 1912 von Birkhoff eingeführten chromatischen Polynoms eines Graphen stellt bekanntlich ein NP-vollständiges Problem dar. Dieses gilt somit erst recht für die Verallgemeinerung des chromatischen Polynoms zum bivariaten chromatischen Polynom nach Dohmen, Pönitz und Tittmann aus dem Jahre 2003. Eine von Averbouch, Godlin und Makowsky 2008 vorgestellte Rekursionsformel verursacht durch wiederholte Anwendung im Allgemeinen einen exponentiellen Rechenaufwand. Daher war das Ziel der vorliegenden Dissertation, Vereinfachungen zur Berechnung des bivariaten chromatischen Polynoms spezieller Graphentypen zu finden. Hierbei wurden folgende Resultate erzielt: Für Vereinigungen von Sternen, für vollständige Graphen, aus welchen die Kanten von Sternen mit paarweise voneinander verschiedenen Ecken gelöscht wurden, für spezielle Splitgraphen und für vollständig partite Graphen konnten rekursionsfreie Gleichungen zur Berechnung des bivariaten chromatischen Polynoms mit jeweils linear beschränkter Rechenzeit gefunden werden. Weiterhin werden Möglichkeiten der Reduktion allgemeiner Splitgraphen, bestimmter bipartiter Graphen sowie vollständig partiter Graphen vorgestellt. Bei letzteren erweist sich eine hierbei gefundene Rekursionsformel durch eine polynomiell beschränkte Laufzeit als effektive Methode. Ferner konnte in einem Abschnitt zu Trennern in Graphen gezeigt werden, dass der Spezialfall der trennenden Cliquen, welcher im univariaten Fall sehr einfach ist, im bivariaten Fall sehr komplexe Methoden erfordert. Ein Zusammenhang zwischen dem bivariaten chromatischen Polynom und dem Matchingpolynom wurde für vollständige Graphen, welchen die Kanten von Sternen mit paarweise voneinander verschiedenen Ecken entnommen wurden, sowie für Bicliquen hergestellt. Die vorliegende Dissertation liefert darüber hinaus auch einige Untersuchungen zum trivariaten chromatischen Polynom, welches auf White (2011) zurückgeht und eine weitere Verallgemeinerung des bivariaten chromatischen Polynoms darstellt. Hierbei konnte gezeigt werden, dass dessen Berechnung selbst für einfache Graphentypen schon recht kompliziert ist. Dieses trifft sogar dann noch zu, wenn man die einzelnen Koeffizienten als bivariate Polynome abspaltet und einzeln berechnet. Abschließend stellt die Arbeit zu vielen Resultaten Implementierungen mit dem Computeralgebrasystem Mathematica bereit, welche zahlreiche Möglichkeiten zu eigenständigen Versuchen bieten.

River ecosystems at risk

Worldwide water managers are increasingly challenged to allocate sufficient and affordable water supplies to different water use sectors without further degrading river ecosystems and their valuable services to mankind. Since 1950 human population almost tripled, water abstractions increased by a factor of four, and the number of large dam constructions is about eight times higher today. From a hydrological perspective, the alteration of river flows (temporally and spatially) is one of the main consequences of global change and further impairments can be expected given growing population pressure and projected climate change. Implications have been addressed in numerous hydrological studies, but with a clear focus on human water demands. Ecological water requirements have often been neglected or addressed in a very simplistic manner, particularly from the large-scale perspective. With his PhD thesis, Christof Schneider took up the challenge to assess direct (dam operation and water abstraction) and indirect (climate change) impacts of human activities on river flow regimes and evaluate the consequences for river ecosystems by using a modeling approach. The global hydrology model WaterGAP3 (developed at CESR) was applied and further developed within this thesis to carry out several model experiments and assess anthropogenic river flow regime modifications and their effects on river ecosystems. To address the complexity of ecological water requirements the assessment is based on three main ideas: (i) the natural flow paradigm, (ii) the perception that different flows have different ecological functions, and (iii) the flood pulse concept. The thesis shows that WaterGAP3 performs well in representing ecologically relevant flow characteristics on a daily time step, and therefore justifies its application within this research field. For the first time a methodology was established to estimate bankfull flow on a 5 by 5 arc minute grid cell raster globally, which is a key parameter in eFlow assessments as it marks the point where rivers hydraulically connect to adjacent floodplains. Management of dams and water consumption pose a risk to floodplains and riparian wetlands as flood volumes are significantly reduced. The thesis highlights that almost one-third of 93 selected Ramsar sites are seriously affected by modified inundation patterns today, and in the future, inundation patterns are very likely to be further impaired as a result of new major dam initiatives and climate change. Global warming has been identified as a major threat to river flow regimes as rising temperatures, declining snow cover, changing precipitation patterns and increasing climate variability are expected to seriously modify river flow regimes in the future. Flow regimes in all climate zones will be affected, in particular the polar zone (Northern Scandinavia) with higher river flows during the year and higher flood peaks in spring. On the other side, river flows in the Mediterranean are likely to be even more intermittent in the future because of strong reductions in mean summer precipitation as well as a decrease in winter precipitation, leading to an increasing number of zero flow events creating isolated pools along the river and transitions from lotic to lentic waters. As a result, strong impacts on river ecosystem integrity can be expected. Already today, large amounts of water are withdrawn in this region for agricultural irrigation and climate change is likely to exacerbate the current situation of water shortages.